package com.chenxys.algorithm.leetcode;

import com.chenxys.algorithm.common.ArrUtils;
import com.chenxys.algorithm.common.IntegerUtils;

import java.util.List;

/**
 * <p>
 *      <a href="https://leetcode.cn/problems/sum-of-values-at-indices-with-k-set-bits/">计算K置位下标对应元素的和</a><br/>
 *      给你一个下标从0开始的整数数组nums和一个整数k。<br/>
 * 　　 请你用整数形式返回nums中的特定元素之和，这些特定元素满足：其对应下标的二进制表示中恰存在k个置位。<br/>
 * 　　 整数的二进制表示中的1就是这个整数的置位。<br/>
 * 　　 例如，21的二进制表示为10101，其中有3个置位。<br/>
 *      例: <br/>
 *          输入: nums = [5,10,1,5,2], k = 1<br/>
 *          输出: 13<br/>
 *          解释: 下标的二进制表示是： <br/>
 *                  0 = 0002<br/>
 *                  1 = 0012<br/>
 *                  2 = 0102<br/>
 *                  3 = 0112<br/>
 *                  4 = 1002 <br/>
 *          下标 1、2 和 4 在其二进制表示中都存在 k = 1 个置位。<br/>
 * 因此，答案为 nums[1] + nums[2] + nums[4] = 13 。<br/>
 * </p>
 * @author Chenxys
 * @version V1.0
 * @Package com.chenxys.algorithm.leetcode
 * @date 2024/1/25 14:15
 * @Copyright ©
 */
@SuppressWarnings("all")
public class LeetCode363 {

    /**
     * <p>
     *     计算K置位下标对应元素的和
     * </p>
     */
    public static  int sumIndicesWithKSetBits(List<Integer> nums, int k) {
        int N = nums.size();
        int res = 0;
        for (int i = 0; i < N; i++) {
            if (k == Integer.bitCount(i)) {
                res += nums.get(i);
            }
        }
        return res;
    }


    /**
     * <p>
     *     计算K置位下标对应元素的和
     * </p>
     */
    public static int checkSumIndicesWithKSetBits(List<Integer> nums, int k) {
        int ans = 0;
        for (int i = 0; i < nums.size(); ++i) {
            if (bitCount(i) == k) {
                ans += nums.get(i);
            }
        }
        return ans;
    }

    /**
     * <p>
     *     返回二进制数中1的个数
     * </p>
     * @param x 待获取的数
     * @return x转为二进制后1的个数
     */
    public static int bitCount(int x){
        int cut = 0;
        while (x != 0) {
            cut += (x % 2);
            x /= 2;
        }
        return cut;
    }

    public static void main(String[] args) {
        int maxSize = 100;
        int maxVal = 100;
        int testTimes = 10000;
        System.out.println("Test Start!");
        List<Integer> list = null;
        for (int i = 0; i < testTimes; i++) {
            list = ArrUtils.generateRandomList(maxSize, maxVal);
            int k = (int) (Math.random()) * 10;
            if (sumIndicesWithKSetBits(list, k) != checkSumIndicesWithKSetBits(list, k)) {
                System.out.println("Oops!");
                list.stream().forEach(s -> System.out.println(s + "\t"));
                System.out.println();
                break;
            }
        }
        System.out.println("Test End!");
    }
}
